package leetcode;

import java.util.*;

public class l0347_前K个高频元素_2_桶排序 {

    public int[] topKFrequent(int[] nums, int k) {
        int[] resultArr = new int[k];
        if (nums == null || nums.length == 0) {
            return resultArr;
        }
        //元素的值 作为key，该元素出现的次数作为value
        Map<Integer, Integer> dataMap = new HashMap<>();
        for (int num : nums) {
            Integer count = dataMap.getOrDefault(num, 0);
            dataMap.put(num, count + 1);
        }
        //元素出现的次数==桶的编号;将出现元素的值放进桶中
        List<Integer>[] buckets = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : dataMap.entrySet()) {
            //取到第几号桶
            List<Integer> bucket = buckets[entry.getValue()];
            if (bucket == null) {
                bucket = new ArrayList<>();
            }
            bucket.add(entry.getKey());
            //将几号桶的赋值回桶集合中
            buckets[entry.getValue()] = bucket;
        }
        List<Integer> resultList = new ArrayList<>();
        for (int i = buckets.length - 1; i > 0; i--) {
            if (resultList.size() == k) {
                break;
            }
            if (buckets[i] != null) {
                resultList.addAll(buckets[i]);
            }
        }
        for (int i = 0; i < resultList.size(); i++) {
            resultArr[i] = resultList.get(i);
        }
        return resultArr;
    }
}
